package com.yun.algorithmproblem.leetcode;

/**
 * 3083. 字符串及其反转中是否存在同一子字符串
 * <p>
 * 给你一个字符串 s ，请你判断字符串 s 是否存在一个长度为 2 的子字符串，在其反转后的字符串中也出现。
 * <p>
 * 如果存在这样的子字符串，返回 true；如果不存在，返回 false 。
 */
public class Leetcode3083 {

    public static void main(String[] args) {
        Leetcode3083 obj = new Leetcode3083();
        String s = "leetcode";
        obj.isSubstringPresent(s);
    }

    public boolean isSubstringPresent(String s) {
        int[][] dp = new int[s.length()][s.length()];
        char[] sCharArray = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            if (sCharArray[s.length() - 1] == sCharArray[i]) {
                dp[0][i] = 1;
            }
        }
        for (int i = 1; i < s.length(); i++) {//竖
            char c = sCharArray[s.length() - 1 - i];
            if (c == sCharArray[0]) {
                dp[i][0] = 1;
            }
            for (int j = 1; j < s.length(); j++) {//横
                if (c ==sCharArray[j]){
                    dp[i][j]=dp[i-1][j-1]+1;
                    if(dp[i][j]>=2){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
